package day0411

func spiralOrder(matrix [][]int) (ans []int) {
	m, n := len(matrix), len(matrix[0])
	row, column := 0, 0
	directionIndex := 0
	total := m * n

	directions := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
	visited := make([][]bool, m)
	for i := 0; i < m; i++ {
		visited[i] = make([]bool, n)
	}

	for i := 0; i < total; i++ {
		visited[row][column] = true
		ans = append(ans, matrix[row][column])

		// 探索下一个位置， 若位置不合法 ，换方向
		nextRow, nextColumn := row+directions[directionIndex][0], column+directions[directionIndex][1]
		if nextRow < 0 || nextRow >= m || nextColumn < 0 || nextRow >= n || visited[nextRow][nextColumn] {
			directionIndex++
			directionIndex %= 4
		}
		row, column = row+directions[directionIndex][0], column+directions[directionIndex][1]
	}
	return
}
